package com.rimuru.datastructure.linkedlist;

/**
 * 有序链表去重
 */
public class E05Leetcode82 {

    // 方法1
    public ListNode deleteDuplicates1(ListNode p) {
        if (p == null || p.next == null) {
            return p;
        }
        if (p.val == p.next.val) {
            // 从p开始的第三个元素开始寻找不同的元素
            ListNode x = p.next.next;
            while (x != null && x.val == p.val) {
                x = x.next;
            }
            // 找到与p不同的元素x
            return deleteDuplicates1(x);
        } else {
            p.next = deleteDuplicates1(p.next);
            return p;
        }

    }

    /*
        p1 p2 p3
        s, 1, 1, 1, 2, 3, null

        p1 p2    p3
        s, 1, 1, 1, 2, 3, null

        p1 p2       p3
        s, 1, 1, 1, 2, 3, null

        p1 p3
        s, 2, 3, null

        p1 p2 p3
        s, 2, 3, null

           p1 p2 p3
        s, 2, 3, null
     */
    // 方法2
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode s = new ListNode(-1, head);
        ListNode p1 = s;
        ListNode p2, p3;
        while ((p2 = p1.next) != null && (p3 = p2.next) != null) {
            if (p2.val == p3.val) {
                // 寻找与p2不同的元素
                while ((p3 = p3.next) != null && p3.val == p2.val) {}
                // 此刻 p3 与 p2不同
                p1.next = p3;
                // 此时不需要移动p1 因为找到的下一位可能还是重复的!
            } else {
                p1 = p1.next;
            }
        }
        return s.next;
    }

    public static void main(String[] args) {
        ListNode head = ListNode.of(1, 1, 2, 3);
//        ListNode head = ListNode.of(1, 1, 1, 2, 3);
        System.out.println(head);
        System.out.println(new E05Leetcode82().deleteDuplicates(head));
    }
}
